In the analysis of network vulnerability to attack, considering vulnerabilities in isolation is insufficient. This is because attackers often combine exploits against multiple vulnerabilities in order to reach their goals. While a single vulnerability may not pose a significant threat to a network, a combination of vulnerabilities may. Thus even well administered networks can be vulnerable to attacks, because of the security ramifications of offering a variety of combined services.
An approach to this problem is to build a model of global network security, e.g., as a state machine with security conditions as variables and attacker exploits as transitions. Various methods have been proposed for finding attack paths (sequences of exploit state transitions) in such models, including symbolic model checker (logic-based) approaches [1] [2] [3] [4], and graph-based approaches [5] [6] [7] [8] [9]. However, such methods generally have serious scalability problems, since they must contend with the exponential complexity of the full security state search space.
More recently [10] [11], it has been recognized that under an assumption of monotonic logic, it is not necessary to represent attack paths (usually organized as graphs) explicitly. Instead, the dependencies among exploits and security conditions may encode the same information provided by attack graphs. Monotonic logic may lead to an efficient (low-order polynomial) exploit dependency graph representation that scales well. Semantically, monotonic logic simply means that the attacker need not relinquish resources already gained in order to further advance the attack. This can be a valid modeling decision, corresponding to the observation that the control that attackers exert over networks effectively increases monotonically over time.
Attack graphs (and even exploit dependency graphs) show sequences of exploits, which may be useful for applications that focus on the attacks themselves. But network administrators usually don't care about exploit sequences—they just want to know the best way to harden their network. What is needed is an explicit and manageable set of network hardening options that provide for the safety of given network resources.